package leetcode.d_200_299;

public class P208 {
    class Trie {
        boolean isEnd;
        Trie[] children;

        public Trie() {
            this.children = new Trie[26];
        }

        public void insert(String word) {
            char[] chars = word.toCharArray();
            Trie node = this;
            for (char ch : chars) {
                int idx = ch - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
            }
            node.isEnd = true;
        }

        public boolean search(String word) {
            Trie node = searchPrefix(word);
            return node != null && node.isEnd;
        }

        public boolean startsWith(String prefix) {
            Trie node = searchPrefix(prefix);
            return node != null;
        }

        private Trie searchPrefix (String prefix) {
            char[] chars = prefix.toCharArray();
            Trie node = this;
            for (char ch : chars) {
                int idx = ch - 'a';
                if (node.children[idx] == null) {
                    return null;
                }
                node = node.children[idx];
            }
            return node;
        }
    }
}
